package class04;

/**
 * @Auther: xw
 * @Create: 2022/3/10 10:42
 * @Description: 反转一个链表的k个节点
 */
public class RevereNodeInKGroup {
    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    /**
     * 获取要转换的k个节点
     * @param start
     * @param k
     * @return 返回此次需要转换的最后一个节点
     */
    public static ListNode getKGroupEnd(ListNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    /**
     *  反转节点
     * @param start 开始节点
     * @param end 结束节点
     */
    public static void reverse(ListNode start, ListNode end){
        end = end.next;//转换为之后的末尾节点需要指向后边的节点
        ListNode pre = null;
        ListNode next = null;
        ListNode cur = start;
        while(cur != end){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

    public static ListNode reverseKGroup(ListNode head, int  k ){
        ListNode start = head;
        ListNode end = getKGroupEnd(start,k);
        if(null == end){
            return head;
        }
        //凑齐了一组
        head = end;
        reverse(start,end);
        //上一组的结尾节点
        ListNode lastEnd = head;
        while(lastEnd.next != null){
            start = lastEnd.next;
            end = getKGroupEnd(start,k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

}
